#include <iostream>

struct Node
{
    int _val;
    Node* _next;

    Node(int val) :_val(val), _next(nullptr){}
};

//创建链表
Node* CreateList()
{
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    Node* node4 = new Node(4);
    Node* node5 = new Node(5);
    Node* node6 = new Node(6);

    node1->_next = node2;
    node2->_next = node3;
    node3->_next = node4;
    node4->_next = node5;

    node5->_next = node3;

    return node1;
}

//判断是否有环,有的话返回相遇的节点
Node* MeetingNode(Node* phead)
{
    if(phead == nullptr)
        return nullptr;
    
    Node* slow = phead;
    Node* fast = phead->_next;

    while(fast != nullptr)
    {
        if(fast == slow)
            return fast;
        
        slow = slow->_next;
        fast = fast->_next;
        if(fast != nullptr)
            fast = fast->_next;
    }
    return nullptr;
}   

//找到环的入口
Node* FindEntryNode(Node* phead)
{
    if(phead == nullptr)
        return nullptr;

    //先计算环中有多少个节点
    Node* meeting_node = MeetingNode(phead);
    if(meeting_node == nullptr)
        return nullptr;

    Node* next = meeting_node->_next;
    unsigned int count = 1;
    while(next != meeting_node)
    {
        count++;
        next = next->_next;
    }

    if(count == 1)
        return meeting_node;
    
    //找到环的入口
    Node* slow = phead;
    Node* fast = phead;
    while(count > 0)
    {
        fast = fast->_next;
        count--;
    }
    
    while(fast != slow)
    {
        slow = slow->_next;
        fast = fast->_next;
    }
    return slow;
}

int main()
{
    Node* head = CreateList();
    std::cout << FindEntryNode(head)->_val << std::endl;
    return 0;
}